/**
 * --------题目描述--------
 * 
 * 小易经常沉迷于网络游戏.
 * 有一次,他在玩一个打怪升级的游戏,他的角色的初始能力值为 a.
 * 在接下来的一段时间内,他将会依次遇见n个怪物,每个怪物的防御力为b1,b2,b3...bn. 
 * 如果遇到的怪物防御力bi小于等于小易的当前能力值c,那么他就能轻松打败怪物,并且使得自己的能力值增加bi;
 * 如果bi大于c,那他也能打败怪物,但他的能力值只能增加bi与c的最大公约数.
 * 那么问题来了,在一系列的锻炼后,小易的最终能力值为多少?
 * 
 * --------输入描述-------
 * 对于每组数据，第一行是两个整数n[1,100000)表示怪物的数量和a表示小易的初始能力值
 * 第二行n个整数，b1,b2,b3...bn(bi[1,n])表示每个怪物的防御力
 * 
 * 
 * --------输出描述-------
 * 对于每组数据,输出一行.每行仅包含一个整数,表示小易的最终能力值c
 * 
 */
package me.yobol.algorithm.inaction.netease;

import java.util.Scanner;

/**
 * 该问题难点在于最大公约数(Great Common Divisor)的求取。
 * 
 * 
 * @author Yobol
 */
public class TheRoad2Upgrade {
    
    /**
     * 求两个整数的最大公约数
     * 
     * 欧几里得算法——辗转相除算法
     * 定理：gcd(a,b) = gcd(b,a % b)
     * 证明：a可以表示成a = kb + r，则r = a mod b 
     * 假设d是a,b的一个公约数，则有
     * d|a,d|b（d能被a，b整除），而r = a - kb，因此d|r（因为r=a - kb，所以d一定也能被r整除），因此d是(b,a mod b)的公约数
     * 假设d是(b,a mod b)的公约数，则 
     * d|b,d|r，但是a = kb + r，因此d也是(a,b)的公约数
     * 因此(a,b)和(b,a mod b)的公约数是一样的，其最大公约数也必然相等，得证
     * 
     * 
     * 
     * 欧几里德算法是计算两个数最大公约数的传统算法，他无论从理论还是从效率上都是很好的。但是他有一个致命的缺陷，这个缺陷只有在大素数时才会显现出来。 
     * 考虑现在的硬件平台，一般整数最多也就是64位，对于这样的整数，计算两个数之间的模是很简单的。
     * 对于字长为32位的平台，计算两个不超过32位的整数的模，只需要一个指令周期，而计算64位以下的整数模，也不过几个周期而已。
     * 但是对于更大的素数，这样的计算过程就不得不由用户来设计，
     * 为了计算两个超过64位的整数的模，用户也许不得不采用类似于多位数除法手算过程中的试商法，
     * 这个过程不但复杂，而且消耗了很多CPU时间。
     * 对于现代密码算法，要求计算128位以上的素数的情况比比皆是，设计这样的程序迫切希望能够抛弃除法和取模。
     * 注：说到抛弃除法和取模，其实辗转相除法可以写成减法的形式
     * Stein算法由J. Stein 1961年提出，这个方法也是计算两个数的最大公约数。和欧几里德算法 算法不同的是，Stein算法只有整数的移位和加减法，这对于程序设计者是一个福音。 
     * 
     * @param a
     * @param b
     * @return 
     */
    private static int gcd(int a,int b){
        if(b == 0)
            return a;
        return gcd(b, a % b);
    }
    
    private static int gcd1(int a,int b){
        int min = a >= b ? b : a;
        for(int j = min;j > 0;j--){
            if(a % j == 0 &&  b % j == 0){
                return j;
            }
        }
        return 1;
    }
    
    /**
     * 获得小易的能力值
     * 
     * @param n
     * @param a
     * @param defenseOfMonsters
     * @return 
     */
    public static int getAbilityValue(int n,int a,int[] defenseOfMonsters) throws IllegalStateException{
        if(n < 1 || n >= 100000){
            throw new IllegalStateException("怪物数量从1到99999！");
        }
        int c = a;
        for(int i = 0;i < n;i++){
            if (defenseOfMonsters[i] < 1 || defenseOfMonsters[i] > n) {
                throw new IllegalStateException("怪物防御力从1到" + n + "！");
            }
            if (defenseOfMonsters[i] <= c) {
                c += defenseOfMonsters[i];
            }else{
                c += gcd1(c,defenseOfMonsters[i]);
            }
        }
        return c;
    }
    
    /**
     * 输入
     *      4 3
     *      1 2 3 4
     * 输出
     *      13
     */
    public static void main(String[] args) {
        int n = 0;
        int a = 0,c;
        int[] b = null;
        //首先构造对应的输入数据
        Scanner scanner = new Scanner(System.in);
        //获取数据
        while (scanner.hasNextInt()) {
            //输入第一行数据
            n = scanner.nextInt();
            a = scanner.nextInt();
            c = a;
            
            //输入第二行数据
            b = new int[n];
            for (int i = 0; i < n; i++) {
                b[i] = scanner.nextInt();
            }
            
            try {
                c = getAbilityValue(n, a, b);
            } catch (IllegalStateException e) {
                e.printStackTrace(System.out);
            }
            System.out.println("c = " + c);
        }
        scanner.close();
        
        
    }
}
